Paper 2019/403

Fast and simple constant-time hashing to the BLS12-381 elliptic curve

Riad S. Wahby and Dan Boneh

Abstract

Pairing-friendly elliptic curves in the Barreto-Lynn-Scott family are seeing a resurgence in popularity because of the recent result of Kim and Barbulescu that improves attacks against other pairing-friendly curve families. One particular Barreto-Lynn-Scott curve, called BLS12-381, is the locus of significant development and deployment effort, especially in blockchain applications. This effort has sparked interest in using the BLS12-381 curve for BLS signatures, which requires hashing to one of the groups of the bilinear pairing defined by BLS12-381. While there is a substantial body of literature on the problem of hashing to elliptic curves, much of this work does not apply to Barreto-Lynn-Scott curves. Moreover, the work that does apply has the unfortunate property that fast implementations are complex, while simple implementations are slow. In this work, we address these issues. First, we show a straightforward way of adapting the ``simplified SWU'' map of Brier et al. to BLS12-381. Second, we describe optimizations to this map that both simplify its implementation and improve its performance; these optimizations may be of interest in other contexts. Third, we implement and evaluate. We find that our work yields constant-time hash functions that are simple to implement, yet perform within 9% of the fastest, non--constant-time alternatives, which require much more complex implementations.

Note: Add an optimization due to Michael Scott (Section 5); update and expand evaluation (Section 6)

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in TCHES 2019
DOI
10.13154/tches.v2019.i4.154-179
Keywords
hash functionselliptic curve cryptosystemimplementation
Contact author(s)
rsw @ cs stanford edu
History
2019-09-30: last of 2 revisions
2019-04-22: received
See all versions
Short URL
https://ia.cr/2019/403
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/403,
      author = {Riad S.  Wahby and Dan Boneh},
      title = {Fast and simple constant-time hashing to the {BLS12}-381 elliptic curve},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/403},
      year = {2019},
      doi = {10.13154/tches.v2019.i4.154-179},
      url = {https://eprint.iacr.org/2019/403}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.